package com.tgy.programmer_code_interview_guide._02_linkedList;

import com.tgy.leetcode.ListNode;
import com.tgy.leetcode.TreeNode;

import java.util.Stack;

/**
 * @Author: tgy
 * @Date: 1/27/21 1:43 PM
 */
public class _12_将搜索二叉树转换成链表_01 {

    public static TreeNode searchBinaryTreeToLinkedList(TreeNode treeNode) {

        if (treeNode == null) {

            return treeNode;
        }

        TreeNode lastNode = traversal(treeNode);
        TreeNode rootNode = lastNode.right;
        lastNode.right = null;
        return rootNode;
    }

    public static TreeNode traversal(TreeNode treeNode) {

        if (treeNode == null) {

            return null;
        }

        TreeNode leftLinked = traversal(treeNode.left);
        TreeNode rightLinked = traversal(treeNode.right);

        return linkTreeNode(leftLinked,treeNode,rightLinked);
    }

    public static TreeNode linkTreeNode(TreeNode leftLinked,TreeNode centerNode,TreeNode rightLinked) {

        TreeNode headNode = centerNode;
        if (leftLinked != null) {

             headNode = leftLinked.right;
             leftLinked.right = centerNode;
        }
        centerNode.left = leftLinked;

        TreeNode tailNode = centerNode;
        if (rightLinked != null) {

            tailNode = rightLinked;
            centerNode.right = rightLinked.right;
            centerNode.right.left = centerNode;
        }

        tailNode.right = headNode;

        return tailNode;
    }

    public static void main(String[] args) {

        TreeNode root = new  TreeNode(3);

        root.left = new TreeNode(1);
        root.right = new TreeNode(5);
        root.left.right = new TreeNode(2);
        root.right.left = new TreeNode(4);

        TreeNode node = searchBinaryTreeToLinkedList(root);

//        System.out.println(node);
        while (node != null) {

            System.out.println(node.val);
            node = node.right;
        }
    }
}
